import java.util.ArrayList;
/*
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
则重建二叉树并返回。

思路：
递归
*/

// Definition for binary tree
class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

public class Solution {
   
    public TreeNode reConstructBinaryTree(int [] pre,int pre_start, int pre_end, int[] in, int in_start, int in_end){
        TreeNode root = null;
        int in_mid = 0;
        if(pre_end-pre_start>0 && in_end-in_start>0){
            root = new TreeNode(pre[pre_start]);
            for(int i=in_start; i<in_end; i++){
                if(in[i] == pre[pre_start]){
                    break;
                }else{
                    in_mid++;
                }
            }
            root.left = reConstructBinaryTree(pre,pre_start+1, pre_start+in_mid+1, in, in_start, pre_start+in_mid);
            root.right = reConstructBinaryTree(pre, pre_start+in_mid+1,pre_end, in, in_start+in_mid+1, in_end);
            return root;
        }else{
            return root;
        }
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return reConstructBinaryTree(pre,0,pre.length,in,0,in.length);
    }

    public static void main(String args[]){
        Solution s = new Solution();
//        Integer pre[] = {1,2,4,7,3,5,6,8};
        int pre[] = {1,2,4,7,3,5,6,8};
        int in[] = {4,7,2,1,5,3,8,6};
        TreeNode root = s.reConstructBinaryTree(pre,in);

        System.out.println("hah");

    }

}